﻿using JESAI.DistributedLock.Internal;
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Threading.Tasks;

namespace JESAI.DistributedLock.ZooKeeper;

internal static class ZooKeeperSequentialPathHelper
{
    /// <summary>
    /// 给定一组子节点名称（<paramref name="childrenNames"/>），过滤它们以仅包含具有前缀 <paramref name="prefix"/> 或 <paramref name="alternatePrefix"/> 的顺序节点。
    /// 
    /// 然后，将节点从最旧到最新排序。在大多数情况下，这种排序可以纯粹使用序列号来完成。然而，由于序列号在 <see cref="int.MaxValue"/> 处翻转，在某些情况下需要更复杂的逻辑来获得正确的排序。
    /// </summary>
    public static async ValueTask<(string Path, int SequenceNumber, string Prefix)[]> FilterAndSortAsync(
        string parentNode,
        IEnumerable<string> childrenNames,
        Func<string, Task<long?>> getNodeCreationTimeAsync,
        string prefix,
        string? alternatePrefix = null)
    {
        var ephemeralChildrenWithPrefix = GetEphemeralChildrenWithPrefix();

        if (ephemeralChildrenWithPrefix.Count == 0) { return Array.Empty<(string, int, string)>(); }

        // 首先，按无符号值排序
        ephemeralChildrenWithPrefix.Sort((a, b) => a.UnsignedSequenceNumber.CompareTo(b.UnsignedSequenceNumber));

        // 接下来，测量每对顺序值之间的差距，看看断点是否明显

        // 这大于uint空间的90%；这种大小的差距只能有一个，如果存在这样的差距
        // 那么我们可以安全地假设这个差距标识了序列的结束

        const uint LargeGapSize = 4_000_000_000u;

        var maxGap = 0u;
        var maxGapEndIndex = -1;
        for (var i = 0; i < ephemeralChildrenWithPrefix.Count; ++i)
        {
            var gapEndIndex = (i + 1) % ephemeralChildrenWithPrefix.Count;
            var gap = unchecked(ephemeralChildrenWithPrefix[gapEndIndex].UnsignedSequenceNumber - ephemeralChildrenWithPrefix[i].UnsignedSequenceNumber);
            if (gap > maxGap)
            {
                maxGap = gap;
                maxGapEndIndex = gapEndIndex;
            }
        }
        if (maxGap >= LargeGapSize)
        {
            return ReorderByLowestIndex(maxGapEndIndex);
        }

        // 最后，退回到通过创建时间确定起点
        var creationTimeTasksByChildPath = ephemeralChildrenWithPrefix.ToDictionary(t => t.Path, t => getNodeCreationTimeAsync(t.Path));
        await Task.WhenAll(creationTimeTasksByChildPath.Values).ConfigureAwait(false);

        ephemeralChildrenWithPrefix.RemoveAll(t => creationTimeTasksByChildPath[t.Path].Result == null); // remove all nodes with no creation time (they no longer exist)
        if (ephemeralChildrenWithPrefix.Count == 0) { return Array.Empty<(string, int, string)>(); }

        var oldestChild = ephemeralChildrenWithPrefix.Select((t, index) => (creationTime: creationTimeTasksByChildPath[t.Path].Result!.Value, index))
            .OrderBy(t => t.creationTime)
            .ThenBy(t => t.index)
            .First();
        return ReorderByLowestIndex(oldestChild.index);

        List<(string Path, uint UnsignedSequenceNumber, string Prefix)> GetEphemeralChildrenWithPrefix()
        {
            var result = new List<(string Path, uint UnsignedSequenceNumber, string Prefix)>();
            foreach (var childName in childrenNames)
            {
                int? childSequenceNumber;
                string? childPrefix;
                if (GetSequenceNumberOrDefault(childName, prefix) is { } prefixSequenceNumber)
                {
                    childSequenceNumber = prefixSequenceNumber;
                    childPrefix = prefix;
                }
                else if (alternatePrefix != null
                    && GetSequenceNumberOrDefault(childName, alternatePrefix) is { } alternatePrefixSequenceNumber)
                {
                    childSequenceNumber = alternatePrefixSequenceNumber;
                    childPrefix = alternatePrefix;
                }
                else
                {
                    childSequenceNumber = null;
                    childPrefix = null;
                }

                if (childPrefix != null)
                {
                    result.Add(($"{parentNode.TrimEnd(ZooKeeperPath.Separator)}/{childName}", unchecked((uint)childSequenceNumber!.Value), childPrefix));
                }
            }

            return result;
        }

        (string Path, int SequenceNumber, string Prefix)[] ReorderByLowestIndex(int lowestIndex)
        {
            var result = new (string Path, int SequenceNumber, string Prefix)[ephemeralChildrenWithPrefix.Count];
            for (var i = 0; i < result.Length; ++i)
            {
                var element = ephemeralChildrenWithPrefix[(i + lowestIndex) % result.Length];
                result[i] = (element.Path, unchecked((int)element.UnsignedSequenceNumber), element.Prefix);
            }
            return result;
        }
    }

    /// <summary>
    /// 如果 <paramref name="pathOrName"/> 的形式为 [.../]prefix{序列号}，则返回序列号。否则，返回 null。
    /// </summary>
    internal static int? GetSequenceNumberOrDefault(string pathOrName, string prefix)
    {
        Invariant.Require(prefix.Length > 0);

        // 在处理子路径名称时，这应该是-1；这意味着我们期望前缀在开始处。
        var prefixStartIndex = pathOrName.LastIndexOf(ZooKeeperPath.Separator) + 1;
        if (pathOrName.IndexOf(prefix, startIndex: prefixStartIndex) != prefixStartIndex)
        {
            return null;
        }

        // 来自 https://zookeeper.apache.org/doc/r3.5.4-beta/zookeeperProgrammers.html#Sequence+Nodes+--+Unique+Naming
        // “计数器的格式为%010d——即10位数字，前面补0（计数器以这种方式格式化是为了简化排序），
        // 例如“<path>0000000001”。有关此功能的示例用法，请参阅队列配方。注意：用于存储下一个序列号的计数器
        // 是一个有符号的int（4字节），由父节点维护，当计数器增加到超过2147483647时会溢出（导致名称为“<path>-2147483648”）。”
        var counterSuffix = pathOrName.Substring(prefixStartIndex + prefix.Length);
        return (
                (counterSuffix.Length == 10 && counterSuffix[0] != '+') // 110位数字；不允许前导 +
                || (counterSuffix.Length == 11 && counterSuffix[0] == '-') // 11位数字必须是 - 后跟10位数字
            )
            && int.TryParse(counterSuffix, NumberStyles.AllowLeadingSign, CultureInfo.InvariantCulture, out var sequenceNumber)
            ? sequenceNumber
            : default(int?);
    }

    public static async Task<long?> GetNodeCreationTimeAsync(this ZooKeeperConnection connection, string path) =>
        (await connection.ZooKeeper.existsAsync(path).ConfigureAwait(false))?.getCtime();
}
